package com.leecode;

/**
 * 96. 不同的二叉搜索树 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
 *
 * 输入: 3 输出: 5
 * 解释:
 * 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
 *
 *    1         3     3      2      1
 *     \       /     /      / \      \
 *      3     2     1      1   3      2
 *     /     /       \                 \
 *    2     1         2                 3
 */
public class Leet96 {
	public static void main(String[] args) {
		new Leet96().numTrees(4);
	}

	/**
	 * 100%,96%,开心
	 * @param n
	 * @return
	 */
	public int numTrees(int n) {
		if(n<=0)return 0;

		if(n==1)return 1;
		int[] dp=new int[n+1];
		dp[0]=1;
		dp[1]=1;
		for(int a=2;a<=n;a++){
			for(int b=1;b<=a;b++){
				dp[a]+=dp[b-1]*dp[a-b];
			}
		}//dp完成了
		return dp[n];
	}

	/**
	 * 1为root时,左树空,剩下2,3,
	 * Func(1)=Func(left)*Func(right)=1*Func(2,3)
	 * Func(2)=1*1
	 * Func(3)=1*1;好像找出规律了?!!但得想个容器方便装1,2,3,方便移除1,方便回溯1.
	 * 刚开始写backTrace的时候,还在想参数左右界,
	 * 4.后来做着做着,想到1,2,3,4,对于4来说,123再怎么变都是4的左树,显然123肯定不想再计算一次吧!!dp来了
	 */
	public int backTrace(int n,int border){

		for(int a=1;a<=n;a++){//0.选择列表,1作为root,2作为root,...
			//1.dosomething
			backTrace(n-1,1);//2.recur
			backTrace(n+1,n);
			//3.backTrace
		}
		return 0;
	}
}
